The current state of the art in content addressable memory (CAM) systems has taken two divergent directions as a result of the existence of two rather different application environments. In the first, CAM are used as high speed lookup tables in the cache memory systems of large computers. This requires a high speed (essentially parallel) examination of the contents and an output indicating a perfect match (a hit), or that no perfect match exists (a miss). Semiconductor chips which perform these functions have been widely available for some time. The second, less common, applicational environment arises in the fields of communication, artificial intelligence and cognitive science. Here content addressable memories are used as a primitive model of the brain, which during recognition is believed to function in a content-addressable manner. In this application, the system is asked to produce the memory which most closely correlates to the input, i.e. recognition. A large number of mathematical models for such functions exist, mostly distributed processing in nature, of which neural models are presently the most popular. A number of artificial neural network (ANN) systems have been reported, mainly comprising VLSI chips.
A conventional CAM finds typical application in the cache and virtual memory systems of computers. In operation, the input word is compared (don't care columns are masked) with the stored array of words in parallel. The output is typically the address of the matching memory word. These memories generally function as a standard RAM when being written, that is, memory words are addressed.
These memories have been implemented with high density in an integrated circuit due to the fact that (for a metal oxide semiconductor process) only nine transistors are required per bit. Additional circuitry is required for address decoding and the resolution of contention. While the masking register provides some measure of flexibility in searching the contents and is capable of allowing the memory to function in a best match manner by setting bits in the masking register to allow a stored word which only partially matches the input to be found.
To find the stored data which most closely matches the input in Hamming distance, using the prior art systems, the input must be matched against the memory array with no mask bits set and if a match is found, it is a perfect one; a single bit must be matched across the mask register, matching at each location; and a match must be conducted for every combination of two, then three and so on, until a match if found.
Obviously, when a large word size is involved, this tedious procedure represents a potentially very time consuming methodology. Thus in the worst case, this highly inefficient scheme would take 2.sup.W, where W is the word length in bits. Note that not only is the average search time quite high, the actual search time would be wildly unpredictable.
Highly connected neural networks have been proposed to implement content-addressable memories (CAMS) which network function in an associative or auto-associative mode. However, such network systems are not merely memories, they are distributed computing machines which are capable of finding the memory vector which most closely correlates to the input vector. While such networks have been constructed in monolithic IC form, the large number of preferably modifiable interconnections and the high connectivity required present formidable obstacles to be overcome. High memory density has been achieved, but at the cost of real-time write capability, or through the use of non standard fabrication techniques. The use of standard VLSI fabrication techniques has generally resulted in low memory densities.
The ability to locate the candidate which most closely matches the input appears important in a number of "human" recognition tasks, and key to the impressive results which the neural networks (both fully connected and layered) have provided.
A memory device which performs such "best match" memory access in a rapid, efficient and reliable manner is thus a major desideratum of artificial intelligence systems and a problem for which a solution is needed.